#include<stdio.h>
#define NOTFOUND -100

int binary_search(int a[],int b[],int key,int low,int high)
{
    int d1,d2;
    for(int i=0;;i++)
    {
        if(b[i]-1>=(high-low))    //提醒点1：这个地方high-low表示长度n
        {
            d1=b[i-1];
            d2=b[i-2];
            break;
        }
    }
    int mid;                    //提醒点2：这个地方high不需要另外对Fib长度进行处理
    while(low<=high)
    {
        mid=low+d1-1;
        if(a[mid]>key)          return binary_search(a,b,key,low,mid-1);
        else if (a[mid]<key)    return binary_search(a,b,key,mid+1,high);
        if(a[mid]==key)         return(mid);
    }
    return(NOTFOUND);
}

int main()
{
    int array[100];
    array[0]=1,array[1]=1;
    for(int i=2;i<100;i++)    array[i]=array[i-1]+array[i-2];
    int n,x,k,d1,d2;
    printf("请输入查找模型数据大小：");
    scanf("%d",&n);
    int database[10000];
    printf("请输入查找模型数据样本：");
    for(int i=0;i<n;i++)
    {
        scanf("%d",&database[i]);
    }
    for(int i=n;i<10000;i++)
    {
        database[i]=10000;
    }
    printf("请输入需要查找的数据:");
    scanf("%d",&x);
    k=binary_search(database,array,x,0,n-1);
    if(k!=100) printf("找到数据,位置为%d",k);
    else       printf("找不到数据%d",x);
}